﻿using System;
using System.Collections.Generic;
using System.Text;

namespace SharpSoft.Geometries
{
    /// <summary>
    /// 由N个点构成的封闭多边形（最后一点和首个点视为连接）
    /// </summary>
    /// <remarks>
    /// 其中多边形三角化使用的耳切法参考<see cref="https://www.geometrictools.com/Samples/Geometrics.html#TriangulationEC"/>。
    ///  参考<see cref="https://github.com/eppz/Unity.Library.eppz.Geometry/blob/master/Model/Polygon.cs"/>
    ///  参考<see cref="https://github.com/eppz/Triangle.NET"/>
    /// </remarks>
    public class Polygon : ICloneable
    {
        public Polygon()
        {

        }
        public Polygon(IEnumerable<Point2D> ps)
        {
            this.Points = new Point2DCollection(ps);
            if (this.Points.Count < 3)
            {
                throw new Exception("the Polygon must contains 3 points at least.");
            }
        }
        /// <summary>
        /// 构成多边形的顶点
        /// </summary>
        public Point2DCollection Points { get; set; }
        /// <summary>
        /// 多边形的子结构（内部空岛）
        /// </summary>
        public List<Polygon> Chiledren { get; } = new List<Polygon>();
        /// <summary>
        /// 索引器支持循环访问
        /// </summary>
        /// <param name="ringIndex"></param>
        /// <returns></returns>
        public Point2D this[int ringIndex]
        {
            get
            {
                if (this.Points == null || this.Points.Count == 0)
                {
                    throw new Exception("polygon is empty.");
                }
                var i = ringIndex % this.Points.Count;
                if (i < 0)
                {
                    i += this.Points.Count;
                }
                return this.Points[i];

            }
            set
            {
                if (this.Points == null || this.Points.Count == 0)
                {
                    throw new Exception("polygon is empty.");
                }
                var i = ringIndex % this.Points.Count;
                if (i < 0)
                {
                    i += this.Points.Count;
                }
                this.Points[i] = value;
            }
        }


        /// <summary>
        /// （耳切法）将多边形三角化(计算构成多边形的所有三角形的顶点顺序),约定多边形顶点顺序的方向为逆时针方向（笛卡尔/右手坐标系中）
        /// </summary>
        /// <returns>返回多边形三角化后的顶点顺序(包含重复顶点，后期按需优化)</returns>
        /// <remarks>
        /// <see cref="https://blog.csdn.net/u010019717/article/details/52753855"/>
        /// </remarks>
        public List<Point2D> Triangulate()
        {
            RingList<Point2D> ps = new RingList<Point2D>(this.Points);

            Func<int, bool> isEar = (index) =>
            {//判断是否为耳尖（该顶点所在的多边形内角<180°）
                var v1 = ps[index] - ps[index - 1];
                var v2 = ps[index + 1] - ps[index];
                var dg = (Degree)Vector2D.AngleBetween(v1, v2);
                return dg >= 0 && dg < 180;
            };

            Func<int, bool> hasInside = (index) =>
            {//测试是否存在任意点位于当前三角形中
                for (int i = 0; i < ps.Count; i++)
                {
                    if (i >= index - 1 && i <= index + 1) continue;
                    if (Trigon2D.IsInsideTrigon(ps[index - 1], ps[index], ps[index + 1], ps[i])) return true;
                }

                return false;
            };
            List<int> inds = new List<int>(ps.Count * 3);
            List<Point2D> points = new List<Point2D>(ps.Count * 3);
            bool canTriangulate = true;

            while (canTriangulate)
            {
                canTriangulate = false;
                for (int i = 0; i < ps.Count; i++)
                {
                    if (isEar(i) && !hasInside(i))
                    {
                        points.Add(ps[i - 1]);
                        points.Add(ps[i]);
                        points.Add(ps[i + 1]);
                        ps.RemoveAt(i);
                        canTriangulate = true;//尚有符合要求的顶点  标记继续迭代查找
                    }
                }
            }
            return points;
        }
        /// <summary>
        /// (回转数法)测试点是否包含在多边形内部
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        /// <remarks> 
        /// 当回转数为 0 时，点在闭合曲线外部。https://blog.csdn.net/Form_/article/details/77855163
        /// </remarks>
        public bool Contains(Point2D p)
        {
            double px = p.X,
                   py = p.Y;
            double sum = 0;

            for (int i = 0, length = this.Points.Count, j = length - 1; i < length; j = i, i++)
            {
                double sx = this.Points[i].X,
                    sy = this.Points[i].Y,
                    tx = this.Points[j].X,
                    ty = this.Points[j].Y;

                // 点与多边形顶点重合或在多边形的边上
                if ((sx - px) * (px - tx) >= 0 && (sy - py) * (py - ty) >= 0 && (px - sx) * (ty - sy) == (py - sy) * (tx - sx))
                {
                    return true;
                }

                // 点与相邻顶点连线的夹角
                var angle = Math.Atan2(sy - py, sx - px) - Math.Atan2(ty - py, tx - px);

                // 确保夹角不超出取值范围（-π 到 π）
                if (angle >= Math.PI)
                {
                    angle = angle - Math.PI * 2;
                }
                else if (angle <= -Math.PI)
                {
                    angle = angle + Math.PI * 2;
                }

                sum += angle;
            }

            // 计算回转数并判断点和多边形的几何关系
            return Math.Round(sum / Math.PI) != 0;
        }

        /// <summary>
        /// 测试另一个多边形是否包含在当前多边形内部（另一个多边形的所有顶点都包含在当前多边形中）
        /// </summary>
        /// <param name="polygon"></param>
        /// <returns></returns>
        public bool Contains(Polygon polygon)
        {
            foreach (var p in polygon.Points)
            {
                if (!this.Contains(p))
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 计算多边形与方向相关的面积
        /// </summary>
        /// <returns></returns>
        public double GetDirectionalArea()
        {
            int n = this.Points.Count;
            var A = 0.0d;
            for (int p = n - 1, q = 0; q < n; p = q++)
            {
                var pval = this.Points[p];
                var qval = this.Points[q];
                A += pval.X * qval.Y - qval.X * pval.Y;
            }
            return (A * 0.5d);
        }
        /// <summary>
        /// TODO:尚未完成 简化当前多边形（如果包含空岛，将空岛与当前多边形合并，返回处理后的单一多边形，如果不包含任何空岛则不作任何处理。）
        /// </summary>
        /// <returns></returns>
        public Polygon Sample()
        {
            if (this.Chiledren.Count == 0)
            {
                return this;
            }
            else
            {
                List<Polygon> children = new List<Polygon>();
                foreach (var item in this.Chiledren)
                {//递归简化
                    Polygon ps = item.Sample();
                    children.Add(ps);
                }

                foreach (var item in children)
                {

                }
            }
            return null;
        }

        /// <summary>
        /// 合并多个嵌套的多边形（多边形嵌套的条件是内部多边形顶点顺序与外部多边形的顶点顺序相反，否则认为两个多边形是不同的多边形，即使他们是包含关系。）
        /// </summary>
        /// <param name="polygons"></param>
        /// <returns></returns>
        public static Polygon[] Combine(IEnumerable<Polygon> polygons)
        {
            List<Polygon> list = new List<Polygon>();
            foreach (var item in polygons)
            {
                list.Add((Polygon)item.Clone());
            }
            var list2 = new List<Polygon>(list);
            for (int i = 0; i < list.Count; i++)
            {
                var item1 = list[i];
                List<Polygon> parents = new List<Polygon>();
                foreach (var item2 in list2)
                {//查找多边形的父级
                    if (item2.Contains(item1) && ((int)item1.GetDirectionalArea() ^ (int)item2.GetDirectionalArea()) < 0/*方向面积进行异或运算，符号相反，结果小于0*/)
                    {
                        parents.Add(item2);
                    }
                }
                Polygon parent = null;
                if (parents.Count == 1)
                {//找到唯一父级
                    parent = parents[0];
                }
                else if (parents.Count > 1)
                {//如果找到多个合理的父级，取其中面积最小的作为有效的父级
                    double minarea = double.PositiveInfinity;

                    foreach (var p in parents)
                    {
                        var area = Math.Abs(p.GetDirectionalArea());
                        if (area < minarea)
                        {
                            parent = p;
                            minarea = area;
                        }
                    }
                }

                if (parent != null)
                {
                    parent.Chiledren.Add(item1);
                    list.Remove(item1);//此多边形已归于它的父级，从链表中移除
                    i--;//回退一步
                }
            }
            //此时，多边形的层级关系已处理完毕，当前链表中只包含位于最外层的多边形
            return list.ToArray();
        }
        /// <summary>
        /// 判断多边形是否为凸多边形
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        public static bool IsConvexPolygon(Point2D[] points)
        {
            if (points == null || points.Length < 3)
            {
                throw new Exception("不是有效的多边形顶点（多边形至少拥有三个顶点）");
            }
            bool? lastLess0 = null;//记录上一个角度是否小于0
            for (int i = 0; i < points.Length; i++)
            {
                var p = points[i];
                var p1 = points[(i + 1) % points.Length];
                var p2 = points[(i + 2) % points.Length];
                Vector2D v1 = p1 - p;
                Vector2D v2 = p2 - p1;
                var angle = (Degree)Vector2D.AngleBetween(v1, v2);

                double v = angle.Optimize360();
                if (lastLess0.HasValue)
                {
                    if (angle < 0 ^ lastLess0.Value)
                    {
                        return false;
                    }
                }
                lastLess0 = angle < 0;
                if (Math.Abs(v) > 180)
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 获取多边形的中心（正外接矩形的中心）
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        public static Point2D GetCenter(IEnumerable<Point2D> points)
        {
            var minx = double.MaxValue;
            var miny = double.MaxValue;
            var maxx = double.MinValue;
            var maxy = double.MinValue;
            foreach (var p in points)
            {
                minx = Math.Min(minx, p.X);
                miny = Math.Min(miny, p.Y);
                maxx = Math.Max(maxx, p.X);
                maxy = Math.Max(maxy, p.Y);
            }
            return new Point2D(minx + (maxx - minx) / 2d, miny + (maxy - miny) / 2d);
        }

        public object Clone()
        {
            var p = new Polygon(this.Points);
            foreach (var item in this.Chiledren)
            {
                p.Chiledren.Add(item);
            }
            return p;
        }
    }
}
